package com.jinan.algorithm.UnionFind;

public class UnionFindTest {
    //  并查集
    class UnionFind {
        private int[] parent; //父节点数组
        private int[] rank; // 树的高度
        private int count;  //  集合数量

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        //  返回x的根节点(路径压缩优化)
        public int find(int x) {
            while (x != parent[x]) {
                parent[x] = find(parent[x]);
                x = parent[x];
            }
            return parent[x];
        }

        // 合并两个元素所在的集合
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) return;
            // 按秩合并：小树合并到大树
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
                rank[rootX] += rank[rootY];
            } else {
                parent[rootX] = rootY;
                rank[rootY] += rank[rootX];
            }
            count--;
        }

        // 返回连通分量数量
        public int getCount() {
            return count;
        }
    }

    /**
     * 1061.按字典序排列最小的的等效字符串 <a href="https://leetcode.cn/problems/lexicographically-smallest-equivalent-string/description/">...</a>
     * 难度：中等
     * tag：并查集 字符串
     * description：给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。
     * 其中  s1[i] 和 s2[i]  是一组等价字符。
     * 举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。
     * 等价字符遵循任何等价关系的一般规则：
     * 自反性 ：'a' == 'a'
     * 对称性 ：'a' == 'b' 则必定有 'b' == 'a'
     * 传递性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'
     * 例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串
     * 利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。
     * restriction:
     * 1 <= s1.length, s2.length, baseStr <= 1000
     * s1.length == s2.length
     * s1 ， s2 和 basestr 仅由小写英文字母组成
     *
     * @param s1      字符串1
     * @param s2      字符串2
     * @param baseStr 基准字符串
     * @return 按字典序排列最小的等效字符串
     */
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int[] parent = new int[26];
        int count = 26;
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        int n = s1.length();
        for (int i = 0; i < n; i++) {
            int x = s1.charAt(i) - 'a';
            int y = s2.charAt(i) - 'a';
            merge(parent, x, y);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < baseStr.length(); i++) {
            sb.append((char) ('a' + find(parent, baseStr.charAt(i) - 'a')));
        }
        return sb.toString();
    }

    public void merge(int[] parent, int x, int y) {
        if (x == y) {
            return;
        }
        int fx= find(parent, x);
        int fy= find(parent, y);
        if(fx < fy){
            parent[fy] = fx;
        }else {
            parent[fx] = fy;
        }
    }

    public int find(int[] parent, int x) {
        int temp = x;
        while (x != parent[x]) {
            x = parent[x];
        }
        parent[temp] = x;
        return x;
    }
}
